This invention relates to solving optimization problems using quantum computer.
Quantum computers have been applied to solution of binary optimization using adiabatic quantum computation, for instance, quantum annealing. An example of such an approach, and a physical realization of a quantum computer to host such an approach is described in US Pat. Pub. 2010/0306142, titled “Methods for Adiabatic Quantum Computation.” This publication, and below referenced patent publications and/or issued patents, are incorporated herein by reference.
A class of binary optimization problems referred to as Polynomial Unconstrained Binary Optimization (PUBO) seeks to find an assignment x∈N, where ={0,1}, such that ƒ(x)=min [ƒ(N)]. The function ƒ(x) has a unique representation as
      f    ⁡          (      x      )        =            ∑              S        ⊆                  {                      1            ,                                                  ⁢            …            ⁢                                                  ,            N                    }                      ⁢                  ⁢                  c        S            ⁢                        ∏                      i            ∈            S                          ⁢                                  ⁢                  x          i                    
The coefficients cS essentially specify ƒ. These coefficients also specify a Hamiltonian H(ƒ). At least some such Hamiltonians may be used to configure a quantum computer (i.e., a physical machine), yielding an electronic solution of the assignment problem corresponding to the Hamiltonian. In at least some implementations and configurations of a quantum computer, each problem variable xi corresponds to a physical element of the quantum computer. The physical (quantum) state of each element is represented as having two basis elements (corresponding to xi=0 and xi=1) and the (complex) coefficient characterize the physical state of the element. Therefore for N variables xi there are 2N complex variables that characterized the physical state of the corresponding elements of the quantum computer. The Hamiltonian represents an operator on the set of the quantum states of the computer elements, which through physical coupling of elements of the computer defines a physical time evolution of the states. When the operators qi of a Hamiltonian
      H    ⁡          (      f      )        =            ∑              S        ⊆                  {                      1            ,                                                  ⁢            …            ⁢                                                  ,            N                    }                      ⁢                  ⁢                  c        S            ⁢                        ∏                      i            ∈            S                          ⁢                                  ⁢                  q          i                    
are coupled with the same coefficients cS as the xi are coupled in ƒ( ), then the vector x that minimizes ƒ( ) corresponds to an eigenvector of the Hamiltonian and the physical computer physically maintains that state.
In practice, there may a number of constraints on the Hamiltonians that can be used to configure a quantum computer. First, the maximum degree of coupling may be limited, for instance, to two, such that there each subset S has at most two elements, such that
      H    ⁡          (      f      )        =            ∑              1        ≤        i        ≤        j        ≤        N              ⁢                  ⁢                  a        ij            ⁢              q        i            ⁢                        q          j                .            
Such Hamiltonians are referred to as “2-local.” In some hardware implementations of quantum computer, a graph whose nodes represent variables xi and links represent pairs of variables that are constrained by non-zero coupling coefficients αij is embedded in a hardware based graphs that implements the constraints. An example of such an approach to graph embedding is described in U.S. Pat. No. 8,244,662, titled “Graph Embedding Techniques.” A second constraint of certain quantum computers is on the precision or range of values cS that may be represented in configuration of the hardware. For example, certain quantum computers are limited to a precision range of 16 values (e.g., ±1, . . . , ±8). A third constraint is that a quantum computer is generally limited in the number of variables xi, each corresponding to a quantum bit represented in a corresponding hardware element in the quantum computer.
In order to apply a quantum computer to a problem that is specified by a k-local form, where k>2 (e.g., k=3), one approach is to introduce ancilla variables. For example, one approach is to transform a 3-local specification on a set of variables x1 to xN, by introducing a set of ancilla variables xij, each corresponding to a pair of variables xi and xj. In this way, terms of the form xixjxk may be replaced with quadratic terms xijxk. In some examples, the problem variable pairs to combine to form the ancilla variables are selected at random.
However, in general, introduction of ancilla variables can easily cause the total number of variables and/or the required precision of the coupling coefficients to exceed the capacity of the quantum computer.